package binary_tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 二叉树的基本操作
 */
class TreeNode<E> {
    //节点值
    E val;
    //左子树的根
    TreeNode<E> left;
    //右子树的根
    TreeNode<E> right;

    public TreeNode(E val) {
        this.val = val;
    }
}

/**
 * 二叉树的建立
 * @param <E>
 */
public class MYbinarytree<E> {

    public TreeNode<Character> root;

    //建立一个简单的二叉树
    public void buildTree(){
        TreeNode<Character> node=new TreeNode<>('A');
        TreeNode<Character> node1=new TreeNode<>('B');
        TreeNode<Character> node2=new TreeNode<>('C');
        TreeNode<Character> node3=new TreeNode<>('D');
        TreeNode<Character> node4=new TreeNode<>('E');
        TreeNode<Character> node5=new TreeNode<>('F');
        TreeNode<Character> node6=new TreeNode<>('G');
        TreeNode<Character> node7=new TreeNode<>('H');
        //连接二叉树
        node.left=node1;
        node.right=node2;
        node1.left=node3;
        node1.right=node4;
        node4.left=node6;
        node6.right=node7;
        node2.right=node5;
        root=node;
    }

    /**
     * 只需要二叉树的根节点，就可以按照前序遍历的方法输出
     * @param root
     */
    public void PreorderTraversal(TreeNode root){
        if (root==null){
            return;
        }
        //根左右,先打印根节点
        System.out.print(root.val+" ");
        //左子树节点的输出交给子函数处理
        PreorderTraversal(root.left);
        //右子树节点的输出交给子函树处理
        PreorderTraversal((root.right));
    }

    /**
     * 只需要二叉树的根节点，就可以按照中序遍历的方法输出
     * @param root
     */
    public void InorderTraversal(TreeNode root){
        if (root==null){
            return;
        }
        //左根右，先递归输出左节点，左节点的输出交给子函数处理
        InorderTraversal(root.left);
        //根节点的输出
        System.out.print(root.val+" ");
        //递归输出右节点，右节点的输出交给子函数处理
        InorderTraversal(root.right);

    }

    /**
     * 只需要二叉树的根节点，就可以按照后序遍历的方法输出
     * @param root
     */
    public void PostordeTraversall(TreeNode root){
        if (root==null){
            return;
        }
        //左右根，先递归输出左节点，左节点的输出交给子函数处理
        PostordeTraversall(root.left);
        //递归输出右节点，右节点的输出交给子函数处理
        PostordeTraversall(root.right);
        //根节点的输出
        System.out.print(root.val+" ");
    }

    /**
     * 传入二叉树的根节点，就可以求出节点个数
     * @param root
     * @return
     */
    public int getNode(TreeNode root){
        if (root==null){
            return 0;
        }
        //此时二叉树不为空,此时知道一个根节点root，那么根节点的左右子树的节点数就交给子函数处理
        //总结点数=1（根节点root）+左子树的所有节点+右子树的所有节点
        return 1+getNode(root.left)+getNode(root.right);
    }

    /**
     * 使用层序遍历统计二叉树的节点数
     * @param root
     * @return
     */
    public int getNodeSequence(TreeNode root){
        if (root==null){
            return 0;
        }
        int size=0;
        Deque<TreeNode> deque=new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()){
            TreeNode ret=deque.poll();
            size++;
            if (ret.left!=null){
                deque.offer(ret.left);
            }
            if (ret.right!=null){
                deque.offer(ret.right);
            }
        }return size;
    }

    /**
     * 传入二叉树的根节点，就可以求职叶子节点数
     * @param root
     * @return
     */
    public int getLeafNode(TreeNode root){
        if (root==null){
            return 0;
        }
        if ((root.left==null)&&(root.right==null)){
            //此时说明只有一个根节点
            return 1;
        }
        //此时root不为空且有子树
        //总叶子节点数=左子树的叶子节点数+右子树的叶子节点数
        return getLeafNode(root.left)+getLeafNode(root.right);
    }

    /**
     * 传入二叉树的根节点，就可以直到第k层的节点个数
     * @param root
     * @param k
     * @return
     */
    public int getKNode(TreeNode root,int k){
        if (root==null||k<0){
            return 0;
        }
        if (k==1){
            //k=1时就是根节点
            return 1;
        }
        //以root为根的第k层节点个数=以root.left为根的第k-1层节点个数+以root.right为根的第k-1层节点个数
        return getKNode(root.left,k-1)+getKNode(root.right,k-1);
    }

    /**
     * 传入二叉树的根节点，就可以知道树的高度
     * @param root
     * @return
     */
    public int rootHeight(TreeNode root){
        if (root==null) {
            return 0;
        }
        //二叉树的高度=1+（左子树高度和右子树高度的最大值）
        return 1+Math.max(rootHeight(root.left),rootHeight(root.right));
    }

    /**
     * 判断二叉树是否包含指定值val
     * @param root
     * @param val
     * @return
     */
    public boolean contains(TreeNode<E> root,E val){
        if (root==null){
            return false;
        }
        //此时根节点就是要找的节点
        if (root.val.equals(val)){
            return true;
        }
        //如果不是根节点，就继续在左子树和右子树查找
        return contains(root.left,val)||contains(root.right,val);
    }

    /**
     * 传入二叉树的根节点，借助队列，就可以按照层序遍历打印
     * @param root
     */
    public void levelOrde(TreeNode<E> root){
        Deque<TreeNode<E>> deque=new LinkedList<>();
        deque.offer(root);
        //循环的终止条件就是队列不为空
        while (!deque.isEmpty()){
            //取出当前层的节点个数
            // 每当进行完一层遍历时，队列中就恰好存储了下一层的所有节点值
            int n=deque.size();
            for (int i = 0; i <n ; i++) {
                TreeNode<E> node=deque.poll();
                System.out.print(node.val+" ");
                //遍历这一层的同时将左右子树添加到队列
                if (node.left!=null){
                    deque.offer(node.left);
                }
                if (node.right!=null){
                    deque.offer(node.right);
                }
                //这一层循环走完恰好队列中存储了下一层的节点值
            }
        }
    }
}
